「PAT甲级真题解析」Advanced Level 1004 Counting Leaves

Table of Contents

问题分析

  1. 题设要求按照从根结点开始自顶向下输出树结构每一层的叶子结点数目。
  2. 这意味着我们需要设置计数器, 然后遍历树的每一个结点, 然后检查该结点是否是叶子结点, 如果是叶子结点, 则将计数器中该层次叶子结点个数+1.
  3. 遍历树结构叶子结点可以用深度优先dfs搜索和广度优先搜索bfs.

完整步骤描述

  1. 获取输入: 树结点总个数, 非叶子结点个数
  2. 初始化记录器:
    • 各个结点的子节点组成记录器
    • 每层叶子结点个数记录器 = {0}
    • 最大层次 = 0
  3. 获取每一个非叶子结点的所有子节点:
    • 获取输入: 非叶子结点的ID, 其子节点个数, 各个子节点ID(记录到记录器中)
  4. 从根结点开始进行深度优先遍历或广度优先遍历(以下使用深度优先遍历):
    • 检查子节点组成记录器中, 该结点是否有子节点:
      • 如果没有, 则该结点为叶子结点:
        • 该层次叶子结点计数+1
        • 检查当前层次是否大于已记录的最大层次, 如果大于则更新记录的最大层次
    • 如果不是叶子结点, 则遍历每一个子节点, 递归进行上述检查
  5. 遍历完毕后, 输出记录的从顶层到最大层次的各个层次叶子结点数目.

伪代码描述

  1. get input: total_node_amount, non_left_node_amount
  2. init recorder/counter:
    • node_to_its_children = []
    • left_node_of_layer = {0}
    • max_depth = 0
  3. for i in range(0, total_node_amount):
    • get input: node_ID, children_amount:
      • for j in range(0, children_amount):
        • get input: child_ID
        • push child_ID into node_to_its_children[node_ID]
  4. dfs(index=1, depth=0):
    • if node_to_its_children[index].size() == 0:
      • left_node_of_layer[depth]++;
      • max_depth = max(max_depth, depth);
      • return;
    • else:
      • for child in node_to_its_children[index]:
        • dfs(child's index, depth+1);
  5. for depth in range(0, max_depth):
    • print(node_to_its_children[depth]);

完整提交代码

1/*
2# 问题分析
31. 题设要求按照从根结点开始自顶向下输出树结构每一层的叶子结点数目。
42. 这意味着我们需要设置计数器, 然后遍历树的每一个结点, 然后检查该结点是否是叶子结点,
5如果是叶子结点, 则将计数器中该层次叶子结点个数+1.
63. 遍历树结构叶子结点可以用深度优先dfs搜索和广度优先搜索bfs.
7
8# 完整步骤描述
91. 获取输入: 树结点总个数, 非叶子结点个数
102. 初始化记录器:
11    - 各个结点的子节点组成记录器
12    - 每层叶子结点个数记录器 = {0}
13    - 最大层次 = 0
143. 获取每一个非叶子结点的所有子节点:
15    - 获取输入: 非叶子结点的ID, 其子节点个数, 各个子节点ID(记录到记录器中)
164. 从根结点开始进行深度优先遍历或广度优先遍历(以下使用深度优先遍历):
17    - 检查子节点组成记录器中, 该结点是否有子节点:
18        - 如果没有, 则该结点为叶子结点:
19            - 该层次叶子结点计数+1
20            - 检查当前层次是否大于已记录的最大层次, 如果大于则更新记录的最大层次
21    - 如果不是叶子结点, 则遍历每一个子节点, 递归进行上述检查
225. 遍历完毕后, 输出记录的从顶层到最大层次的各个层次叶子结点数目.
23
24# 伪代码描述
251. get input: total_node_amount, non_left_node_amount
262. init recorder/counter:
27    - node_to_its_children = []
28    - left_node_of_layer = {0}
29    - max_depth = 0
303. for i in range(0, total_node_amount):
31    - get input: node_ID, children_amount:
32        - for j in range(0, children_amount):
33            - get input: child_ID
34            - push child_ID into node_to_its_children[node_ID]
354. dfs(index=1, depth=0):
36    - if node_to_its_children[index].size() == 0:
37        - left_node_of_layer[depth]++;
38        - max_depth = max(max_depth, depth);
39        - return;
40    - else:
41        - for child in node_to_its_children[index]:
42            - dfs(child's index, depth+1);
435. for depth in range(0, max_depth):
44    - print(node_to_its_children[depth]);
45*/
46
47
48# include<iostream>
49# include<vector>
50using namespace std;
51
52vector<int> node_to_its_children[101];
53int left_node_of_layer[101] = {0};
54int max_depth = 0;
55
56void dfs(int index, int depth){
57    if (node_to_its_children[index].size() == 0){
58        left_node_of_layer[depth]++;
59        max_depth = max(depth, max_depth);
60        return ;
61    }
62    for (int i = 0; i < node_to_its_children[index].size(); i++){
63        dfs(node_to_its_children[index][i], depth+1);
64    }
65}
66
67
68int main(){
69    int total_node_amount, non_left_node_amount;
70    scanf("%d %d", &total_node_amount, &non_left_node_amount);
71    int node_ID, children_amount, child_ID;
72    for (int i = 0; i < non_left_node_amount; i++){
73        scanf("%d %d", &node_ID, &children_amount);
74        for (int j = 0; j < children_amount; j++){
75            scanf("%d", &child_ID);
76            node_to_its_children[node_ID].push_back(child_ID);
77        }
78    }
79
80    dfs(1, 0);
81    printf("%d", left_node_of_layer[0]);
82    for (int i = 1; i <= max_depth; i++){
83        printf(" %d", left_node_of_layer[i]);
84    }
85
86    return 0;
87}
88
Mastodon